#include "main/utils.h"
using namespace std;

class Solution {
  public:
    bool isValid(string s) {
      if (s.size() % 2 == 1) {
        return false;
      }
      unordered_map<char, char> mp = {
        {')', '('},
        {']', '['},
        {'}', '{'},
      };
      stack<char> stk;
      for (auto ch : s) {
        if (mp.count(ch)) {
          if (stk.empty() || stk.top() != mp[ch]) {
            return false;
          }
          stk.pop();
        } else {
          stk.push(ch);
        }
      }
      return stk.empty();
    }
};

int main() {
  string s = "()(){}{}[][]";
  Solution su;
  cout << su.isValid(s) << endl;
}
